NDLI: Efficiently indexing shortest paths by exploiting symmetry in graphs

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

Data integration flows for business intelligence

Optimized union of non-disjoint distributed data sets

Sequenced spatio-temporal aggregation in road networks

Type-based categorization of relational attributes

Rule-based multi-query optimization

Query ranking in probabilistic XML data

GADDI: distance index based subgraph matching in biological networks

Privacy-preserving data mashup

On keys, foreign keys and nullable attributes in relational mapping systems

Scalable stream join processing with expensive predicates: workload distribution and adaptation by time-slicing

A sampling approach for XML query selectivity estimation

It takes variety to make a world: diversification in recommender systems

Sample synopses for approximate answering of group-by queries

$Zerber^{+R}:$ top-k retrieval from a confidential index

G-hash: towards fast kernel-based similarity search in large graph databases

Estimating the number of frequent itemsets in a large database

Flexible and efficient querying and ranking on hyperlinked data sources

A sequential indexing scheme for flash-based embedded systems

Hiding distinguished ones into crowd: privacy-preserving publishing data with outliers

Top-k dominating queries in uncertain databases

Fair, effective, efficient and differentiated scheduling in an enterprise data warehouse

Unrestricted wavelet synopses under maximum error bound

Caching content-based queries for robust and efficient image retrieval

Retrieving meaningful relaxed tightest fragments for XML keyword search

Time-completeness trade-offs in record linkage using adaptive query processing

Reverse k-nearest neighbor search in dynamic and general metric databases

Towards integrated and efficient scientific sensor data processing: a database approach

Efficient provenance storage over nested data collections

A data model for trip planning in multimodal transportation systems

Finding the influence set through skylines

Transactions on the multiversion $B^{+}-tree$

Personalizing entity detection and recommendation with a fusion of web log mining techniques

BaseX & DeepFS joint storage for filesystem and database

CourseCloud: summarizing and refining keyword searches over structured data

Performance evaluation in database research: principles and experience

Shore-MT: a scalable storage manager for the multicore era

Processing probabilistic spatio-temporal range queries over moving objects with uncertainty

AlphaSum: size-constrained table summarization using value lattices

Managing long-running queries

On rewriting XPath queries using views

A novel approach for efficient supergraph query processing on graph databases

On the comparison of microdata disclosure control algorithms

A runtime approach to model-independent schema and data translation

Indexing density models for incremental learning and anytime classification on data streams

Recursion in XQuery: put your distributivity safety belt on

Supporting annotations on relations

A query processor for prediction-based monitoring of data streams

Efficient top-k count queries over imprecise duplicates

On-line exact shortest distance query processing

FOGGER: an algorithm for graph generator discovery

RankClus: integrating clustering with ranking for heterogeneous information network analysis

Secondary bitmap indexes with vertical and horizontal partitioning

An efficient online auditing approach to limit private data disclosure

Evaluating probability threshold k-nearest-neighbor queries over uncertain data

Efficient identification of starters and followers in social media

Distributed similarity search in high dimensions using locality sensitive hashing

An approach to detecting relevant updates to cached data using XML and active databases

Approximate substring selectivity estimation

Interactive query refinement

Top-k dominant web services under multi-criteria matching

Flexible and scalable storage management for data-intensive stream processing

Schema-conscious filtering of XML documents

Parsimonious temporal aggregation

Efficient skyline computation in metric space

Efficient maintenance techniques for views over active documents

Estimating aggregates in time-constrained approximate queries in Oracle

Xoom: a tool for zooming in and out of XML documents

EventSummarizer: a tool for summarizing large event sequences

Geographic privacy-aware knowledge discovery and delivery

Workload-aware data partitioning in community-driven data grids

Anonymizing moving objects: how to hide a MOB in a crowd?

Answering aggregate keyword queries on relational databases using minimal group-bys

Continuous visible nearest neighbor queries

Parallelization of XPath queries using multi-core processors: challenges and experiences

Flexible query answering on graph-modeled data

Detecting privacy violations in database publishing using disjoint queries

A methodology for preference-based personalization of contextual data

Exploiting the power of relational databases for efficient stream processing

Expressive, yet tractable XML keys

Data clouds: summarizing keyword search results over structured data

Flower-CDN: a hybrid P2P overlay for efficient query processing in CDN

The C-ND tree: a multidimensional index for hybrid continuous and non-ordered discrete data spaces

Efficiently indexing shortest paths by exploiting symmetry in graphs

Neighbor-based pattern detection for windows over streaming data

Evaluating very large datalog queries on social networks

Automating the loading of business process data warehouses

Continuous privacy preserving publishing of data streams

PROUD: a probabilistic approach to processing similarity queries over uncertain data streams

A data damage tracking quarantine and recovery (DTQR) scheme for mission-critical database systems

Multiplicative synopses for relative-error metrics

Self-tuning query mesh for adaptive multi-route query processing

Finding frequent co-occurring terms in relational keyword search

Continuous probabilistic nearest-neighbor queries for uncertain trajectories

Ranking objects based on relationships and fixed associations

A view selection algorithm with performance guarantee

Provenance for nested subqueries

Fast object search on road networks

Efficient skyline retrieval with arbitrary similarity measures

Towards materialized view selection for distributed databases

HIDE: heterogeneous information DE-identification

High-performance information extraction with AliBaba

Scalable OLAP and mining of information networks

Efficient constraint evaluation in categorical sequential pattern mining for trajectory databases

LCS-Hist: taming massive high-dimensional data cube compression

MVT: a schema mapping validation tool

Exploiting similarity-aware grouping in decision support systems

A tool for mapping discovery over revealing schemas

MarcoPolo: a community system for sharing and integrating travel information on maps

GCIP: exploiting the generation and optimization of integration processes

NNexus: an automatic linker for collaborative web-based corpora

Efficiently indexing shortest paths by exploiting symmetry in graphs

Content Provider	ACM Digital Library
Author	Wang, Wei Wu, Wentao Xiao, Yanghua Pei, Jian He, Zhenying
Abstract	Shortest path queries (SPQ) are essential in many graph analysis and mining tasks. However, answering shortest path queries on-the-fly on large graphs is costly. To online answer shortest path queries, we may materialize and index shortest paths. However, a straightforward index of all shortest paths in a graph of N vertices takes $O(N^{2})$ space. In this paper, we tackle the problem of indexing shortest paths and online answering shortest path queries. As many large real graphs are shown richly symmetric, the central idea of our approach is to use graph symmetry to reduce the index size while retaining the correctness and the efficiency of shortest path query answering. Technically, we develop a framework to index a large graph at the orbit level instead of the vertex level so that the number of breadth-first search trees materialized is reduced from O(N) to O(\|Δ\|), where \|Δ\| ≤ N is the number of orbits in the graph. We explore orbit adjacency and local symmetry to obtain compact breadth-first-search trees (compact BFS-trees). An extensive empirical study using both synthetic data and real data shows that compact BFS-trees can be built efficiently and the space cost can be reduced substantially. Moreover, online shortest path query answering can be achieved using compact BFS-trees.
Starting Page	493
Ending Page	504
Page Count	12
File Format	PDF
ISBN	9781605584225
DOI	10.1145/1516360.1516418
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-03-24
Publisher Place	New York
Access Restriction	Subscribed
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