NDLI: Fast exact shortest-path distance queries on large networks by pruned landmark labeling

Please wait, while we are loading the content...

Cumulon: optimizing statistical data analysis in the cloud

MESSIAH: missing element-conscious SLCA nodes search in XML data

A scalable lock manager for multicores

Optimal splitters for temporal and multi-version databases

InfoGather+: semantic matching and annotation of numeric and time-varying attributes in web tables

I/O efficient: computing SCCs in massive graphs

An online cost sensitive decision-making method in crowdsourcing systems

Efficient sentiment correlation for large-scale demographics

BitWeaving: fast scans for main memory data processing

Massive graph triangulation

Improving regular-expression matching on strings using negative factors

Towards high-throughput gibbs sampling at scale: a study across storage managers

Quality and efficiency for kernel density estimates in large data

CS2: a new database synopsis for query estimation

Trinity: a distributed graph engine on a memory cloud

NADEEF: a commodity data cleaning system

Photon: fault-tolerant and scalable joining of continuous data streams

Toward practical query pricing with QueryMarket

Recursive mechanism: towards node differential privacy and unrestricted joins

Collective spatial keyword queries: a distance owner-driven approach

Integrating scale out and fault tolerance in stream processing using operator state management

Bolt-on causal consistency

Mind the gap: large-scale frequent sequence mining

Calibrating trajectory data for similarity-based analysis

Fine-grained disclosure control for app ecosystems

Column imprints: a secondary index structure

Big data in capital markets

We are drowning in a sea of least publishable units (LPUs)

Rethinking eventual consistency

Data-driven neuroscience: enabling breakthroughs via innovative data management

GeoDeepDive: statistical inference using familiar data-processing languages

DBalancer: distributed load balancing for NoSQL data-stores

SQUIN: a traversal based query execution system for the web of linked data

The big data ecosystem at LinkedIn

Enhancements to SQL server column stores

LinkBench: a database benchmark based on the Facebook social graph

Query processing on smart SSDs: opportunities and challenges

Split query processing in polybase

FriendRouter: real-time path finder in social networks

SIGMOD 2013 new researcher symposium

Shark: SQL and rich analytics at scale

Indexing for subtree similarity-search using edit distance

Controlled lock violation

Building an efficient RDF store over a relational database

Value invention in data exchange

TF-Label: a topological-folding labeling scheme for reachability querying in a large graph

Leveraging transitive relations for crowdsourced joins

EBM: an entropy-based model to infer social strength from spatiotemporal data

Performance and resource modeling in highly-concurrent OLTP workloads

$Turbo_{iso}:$ towards ultrafast and robust subgraph isomorphism search in large graph databases

String similarity measures and joins with synonyms

Latch-free data structures for DBMS: design, implementation, and evaluation

Efficient ad-hoc search for personalized PageRank

Branch-and-bound algorithm for reverse top-k queries

Characterizing tenant behavior for placement and crisis mitigation in multitenant DBMSs

Don't be SCAREd: use SCalable Automatic REpairing with maximal likelihood and bounded changes

Utility-maximizing event stream suppression

Generalized scale independence through incremental precomputation

PrivGene: differentially private model fitting using genetic algorithms

TOUCH: in-memory spatial join by hierarchical data-oriented partitioning

Quantiles over data streams: an experimental study

RTP: robust tenant placement for elastic in-memory database clusters

Reverse engineering complex join queries

On optimal worst-case matching

Lightweight authentication of linear algebraic queries on data streams

DeltaNI: an efficient labeling scheme for versioned hierarchical data

Managing database technology at enterprise scale

Workload management for big data analytics

TsingNUS: a location-based service system towards live city

Fact checking and analyzing the web

COCCUS: self-configured cost-based query services in the cloud

GRDB: a system for declarative and interactive analysis of noisy information networks

On brewing fresh espresso: LinkedIn's distributed data serving platform

Query containment in entity SQL

BigBench: towards an industry standard benchmark for big data analytics

Micro adaptivity in Vectorwise

Petabyte scale databases and storage systems at Facebook

Adaptive log compression for massive log data

Parallel analytics as a service

Discovering XSD keys from XML data

X-FTL: transactional FTL for SQLite databases

Automatic synthesis of out-of-core algorithms

Indexing methods for moving object databases: games and other applications

Efficiently computing k-edge connected components via graph decomposition

Online search of overlapping communities

ODYS: an approach to building a massively-parallel search engine using a DB-IR tightly-integrated parallel DBMS for higher-level functionality

Fast exact shortest-path distance queries on large networks by pruned landmark labeling

Efficient top-k algorithms for approximate substring matching

DBMS metrology: measuring query time

Provenance-based dictionary refinement in information extraction

On the correct and complete enumeration of the core search space

Minimal MapReduce algorithms

Determining the relative accuracy of attributes

ε-Matching: event processing over noisy sequences in real time

Simulation of database-valued markov chains using SimSQL

Information preservation in statistical privacy and bayesian estimation of unattributed histograms

Finding time period-based most frequent path in big trajectory data

An efficient query indexing mechanism for filtering geo-textual data

Inter-media hashing for large-scale retrieval from heterogeneous data sources

A direct mining approach to efficient constrained graph pattern discovery

Shortest path and distance queries on road networks: towards bridging theory and practice

Knowledge harvesting in the big-data era

WOW: what the world of (data) warehousing can learn from the World of Warcraft

Data mining algorithms as a service in the cloud exploiting relational database systems

Workload optimization using SharedDB

HiNGE: enabling temporal network analytics at scale

Fast data in the era of big data: Twitter's real-time related query suggestion architecture

Timeline index: a unified data structure for processing queries on temporal data in SAP HANA

Building, maintaining, and using knowledge bases: a report from the trenches

Hekaton: SQL server's memory-optimized OLTP engine

Incremental mapping compilation in an object-to-relational mapping system

BUZZARD: a NUMA-aware in-memory indexing system

Machine learning for big data

Rule-based application development using Webdamlog

SONDY: an open source platform for social dynamics mining and analysis

SciQL: array data processing inside an RDBMS

Research-insight: providing insight on research by publication network analysis

Resa: realtime elastic streaming analytics in the cloud

Data management perspectives on business process management: tutorial overview

Speeding up database applications with Pyxis

Interactive data mining with 3D-parallel-coordinate-trees

Iterative parallel data processing with stratosphere: an inside look

QUBLE: blending visual subgraph query formulation with query processing on large networks

Natural language question answering over RDF data

Data stream warehousing

Peckalytics: analyzing experts and interests on Twitter

Stat!: an interactive analytics environment for big data

CARTILAGE: adding flexibility to the Hadoop skeleton

StreamWorks: a system for dynamic graph search

Mobile interaction and query optimizationin a protein-ligand data analysis system

Packing experiments for sharing and publication

PARAS: interactive parameter space exploration for association rule mining

Continuous outlier detection in data streams: an extensible framework and state-of-the-art algorithms

Query processing on prefix trees live

CHIC: a combination-based recommendation system

STEM: a spatio-temporal miner for bursty activity

FAST: differentially private real-time aggregate monitor with filtering and adaptive sampling

xPAD: a platform for analytic data flows

Noah: a dynamic ridesharing system

The farm: where pig scripts are bred and raised

Execution and optimization of continuous queries with cyclops

PBS at work: advancing data management with consistency metrics

A query answering system for data with evolution relationships

LinkIT: privacy preserving record linkage and integration via transformations

Less watts, more performance: an intelligent storage engine for data appliances

The power of data use management in action

Secure database-as-a-service with Cipherbase

A demonstration of SQLVM: performance isolation in multi-tenant relational database-as-a-service

CTrace: semantic comparison of multi-granularity process traces

Fast exact shortest-path distance queries on large networks by pruned landmark labeling

Content Provider	ACM Digital Library
Author	Yoshida, Yuichi Akiba, Takuya Iwata, Yoichi
Abstract	We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search from every vertex. Seemingly too obvious and too inefficient at first glance, the key ingredient introduced here is pruning during breadth-first searches. While we can still answer the correct distance for any pair of vertices from the labels, it surprisingly reduces the search space and sizes of labels. Moreover, we show that we can perform 32 or 64 breadth-first searches simultaneously exploiting bitwise operations. We experimentally demonstrate that the combination of these two techniques is efficient and robust on various kinds of large-scale real-world networks. In particular, our method can handle social networks and web graphs with hundreds of millions of edges, which are two orders of magnitude larger than the limits of previous exact methods, with comparable query time to those of previous methods.
Starting Page	349
Ending Page	360
Page Count	12
File Format	PDF
ISBN	9781450320375
DOI	10.1145/2463676.2465315
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-06-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Query processing Graphs Shortest paths
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in