NDLI: Finding time-dependent shortest paths over large graphs

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

Reality check: a case study of an EII research prototype encountering customer needs

P2P systems with transactional semantics

Scalable XQuery type matching

Schema merging and mapping creation for relational sources

Deleting index entries from compliance storage

Robustness in automatic physical database design

A novel spectral coding in a large graph database

Compacting music signatures for efficient music retrieval

Anonymity for continuous data publishing

XCraft: boosting the performance of active XML materialization

Dynamic skyline queries in metric spaces

Mining all frequent projection-selection queries from a relational table

Schema polynomials and applications

HISSCLU: a hierarchical density-based method for semi-supervised clustering

Ensuring correctness over untrusted private database

Probabilistic ranked queries in uncertain databases

Querying time-series streams

A stratified approach to progressive approximate joins

Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic

OrthoCluster: a new tool for mining synteny blocks and applications in comparative genomics

Data services in your spreadsheet!

$MC^{SE}:$ a multimedia context-based security engine

Flint: Google-basing the Web

BIBEX: a bibliographic exploration tool based on the DEX graph query engine

Streaming in a connected world: querying and tracking distributed data streams

Biocomputational puzzles: data, algorithms, and visualization

Summary management in P2P systems

Engineering succinct DOM

Schema mapping verification: the spicy way

Online recovery in cluster databases

Self-organizing strategies for a column-store database

Fast computing reachability labelings for large graphs with high compression rate

Indexing high-dimensional data in dual distance spaces: a symmetrical encoding approach

Ownership protection of shape datasets with geodesic distance preservation

Exact and inexact methods for selecting views and indexes for OLAP performance improvement

Fast contextual preference scoring of database tuples

Cost-based query optimization for complex pattern mining on multiple databases

Expressive query specification through form customization

Processing transitive nearest-neighbor queries in multi-channel access environments

Data exchange in the presence of arithmetic comparisons

The SBC-tree: an index for run-length compressed sequences

Optimizing on-demand data broadcast scheduling in pervasive environments

Continuous multi-way joins over distributed hash tables

Automatic content targeting on mobile phones

Social ties and their relevance to churn in mobile telecom networks

BeMatch: a platform for matchmaking service behavior models

iDataGuard: middleware providing a secure network drive interface to untrusted internet data storage

Mine your own business, mine others' news!

An inductive database and query language in the relational model

Virtualization and databases: state of the art and research challenges

Building web applications without a database system

Semantic peer, here are the neighbors you want!

Revisiting redundancy and minimization in an XPath fragment

SeMap: a generic mapping construction system

A concurrency control protocol for parallel B-tree structures without latch-coupling for explosively growing digital content

Load distribution of analytical query workloads for database cluster architectures

Finding time-dependent shortest paths over large graphs

The TS-tree: efficient time series search and retrieval

Zerber: r-confidential indexing for distributed documents

Providing freshness guarantees for outsourced databases

Efficient online top-K retrieval with arbitrary similarity measures

On-line discovery of hot motion paths

Synthesizing structured text from logical database subsets

Multi-dimensional search for personal information management systems

SPARQLing constraints for RDF

Efficient LCA based keyword search in XML data

On the brink: searching for drops in sensor data

Ring-constrained join: deriving fair middleman locations from pointsets via a geometric constraint

BI batch manager: a system for managing batch workloads on enterprise data-warehouses

Highly scalable trip grouping for large-scale collective transportation systems

The TELAR mobile mashup platform for Nokia internet tablets

ACCOn: checking consistency of XML write-access control policies

BioScout: a life-science query monitoring system

Quality of service and predictability in DBMS

Taxonomy-superimposed graph mining

Data challenges at Yahoo!

Finding time-dependent shortest paths over large graphs

Content Provider	ACM Digital Library
Author	Yu, Jeffrey Xu Ding, Bolin Qin, Lu
Abstract	The spatial and temporal databases have been studied widely and intensively over years. In this paper, we study how to answer queries of finding the best departure time that minimizes the total travel time from a place to another, over a road network, where the traffic conditions dynamically change from time to time. We study a generalized form of this problem, called the time-dependent shortest-path problem. A time-dependent graph $G_{T}$ is a graph that has an edge-delay function, wi, j(t), associated with each edge $(v_{i},$ $v_{j}),$ to be stored in a database. The edge-delay function wi, j(t) specifies how much time it takes to travel from node $v_{i}$ to node $v_{j},$ if it departs from $v_{i}$ at time t. A user-specified query is to ask the minimum-travel-time path, from a source node, $v_{s},$ to a destination node, $v_{e},$ over the time-dependent graph, $G_{T},$ with the best departure time to be selected from a time interval T. We denote this user query as $LTT(v_{s},$ $v_{e},$ T) over $G_{T}.$ The challenge of this problem is the added complexity due to the time dependency in the time-dependent graph. That is, edge delays are not constants, and can vary from time to time. In this paper, we propose a novel algorithm to find the minimum-travel-time path with the best departure time for a $LTT(v_{s},$ $v_{e},$ T) query over a large graph $G_{T}.$ Our approach outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice. We will discuss the design of our algorithm, together with its correctness and complexity. We conducted extensive experimental studies over large graphs and will report our findings.
Starting Page	205
Ending Page	216
Page Count	12
File Format	PDF
ISBN	9781595939265
DOI	10.1145/1353343.1353371
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-03-25
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