Big Temporally-Detailed Graph Data Analytics
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Big Temporally-Detailed Graph Data Analytics
Published Date
2015-06
Publisher
Type
Thesis or Dissertation
Abstract
Increasingly, temporally-detailed graphs are of a size, variety, and update rate that exceed the capability of current computing technologies. Such datasets can be called Big Temporally-Detailed Graph (Big-TDG) Data. Examples include temporally-detailed (TD) roadmaps which provide typical travel speeds experienced on every road segment for thousands of departure-times in a typical week. Likewise, we have temporally-detailed (TD) social networks which contain a temporal trace of social interactions among the individuals in the network over a time window. Big-TDG data has transformative potential. For instance, a 2011 McKinsey Global Institute report estimates that location-aware data could save consumers hundreds of billions of dollars annually by 2020 by helping vehicles avoid traffic congestion via next-generation routing services such as eco-routing. However, Big-TDG data presents big challenges for the current computer science state of the art. First, Big-TDG data violates the cost function decomposability assumption of current conceptual models for representing and querying temporally-detailed graphs. Second, the voluminous nature of Big-TDG data can violate the stationary ranking-of-candidate-solutions assumption of dynamic programming based techniques such Dijsktra's shortest path algorithm. This thesis proposes novel approaches to address these challenges. To address the first challenge, this thesis proposes a novel conceptual model called, "Lagrangian Xgraphs," which models non-decomposability through a series of overlapping (in space and time) relations, each representing a single atomic unit which retains the required semantics. An initial study shows that Lagrangian Xgraphs are more convenient for representing diverse temporally-detailed graph datasets and comparing candidate travel itineraries. For the second challenge, this thesis proposes a novel divide-and-conquer technique called "critical-time-point (CTP) based approach," which efficiently divides the given time-interval (over which over non-stationary ranking is observed) into disjoint sub-intervals over which dynamic programming based techniques can be applied. Theoretical and experimental analysis show that CTP based approaches outperform the current state of the art.
Description
University of Minnesota Ph.D. dissertation. 2015. Major: Computer Science. Advisor: Shashi Shekhar. 1 computer file (PDF); 142 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Gunturi, Venkata Maruti Viswanath. (2015). Big Temporally-Detailed Graph Data Analytics. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/175447.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.