Search Results

Documents authored by Shekhar, Shashi

Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2024.25
Towards Statistically Significant Taxonomy Aware Co-Location Pattern Detection (Short Paper)

Authors: Subhankar Ghosh, Arun Sharma, Jayant Gupta, and Shashi Shekhar

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
Given a collection of Boolean spatial feature types, their instances, a neighborhood relation (e.g., proximity), and a hierarchical taxonomy of the feature types, the goal is to find the subsets of feature types or their parents whose spatial interaction is statistically significant. This problem is for taxonomy-reliant applications such as ecology (e.g., finding new symbiotic relationships across the food chain), spatial pathology (e.g., immunotherapy for cancer), retail, etc. The problem is computationally challenging due to the exponential number of candidate co-location patterns generated by the taxonomy. Most approaches for co-location pattern detection overlook the hierarchical relationships among spatial features, and the statistical significance of the detected patterns is not always considered, leading to potential false discoveries. This paper introduces two methods for incorporating taxonomies and assessing the statistical significance of co-location patterns. The baseline approach iteratively checks the significance of co-locations between leaf nodes or their ancestors in the taxonomy. Using the Benjamini-Hochberg procedure, an advanced approach is proposed to control the false discovery rate. This approach effectively reduces the risk of false discoveries while maintaining the power to detect true co-location patterns. Experimental evaluation and case study results show the effectiveness of the approach.
Cite as

Subhankar Ghosh, Arun Sharma, Jayant Gupta, and Shashi Shekhar. Towards Statistically Significant Taxonomy Aware Co-Location Pattern Detection (Short Paper). In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 25:1-25:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.COSIT.2024.25,
  author =	{Ghosh, Subhankar and Sharma, Arun and Gupta, Jayant and Shekhar, Shashi},
  title =	{{Towards Statistically Significant Taxonomy Aware Co-Location Pattern Detection}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{25:1--25:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.25},
  URN =		{urn:nbn:de:0030-drops-208404},
  doi =		{10.4230/LIPIcs.COSIT.2024.25},
  annote =	{Keywords: Co-location patterns, spatial data mining, taxonomy, hierarchy, statistical significance, false discovery rate, family-wise error rate}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2023.3
Reducing False Discoveries in Statistically-Significant Regional-Colocation Mining: A Summary of Results

Authors: Subhankar Ghosh, Jayant Gupta, Arun Sharma, Shuai An, and Shashi Shekhar

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Given a set S of spatial feature types, its feature instances, a study area, and a neighbor relationship, the goal is to find pairs <a region (r_{g}), a subset C of S> such that C is a statistically significant regional-colocation pattern in r_{g}. This problem is important for applications in various domains including ecology, economics, and sociology. The problem is computationally challenging due to the exponential number of regional colocation patterns and candidate regions. Previously, we proposed a miner [Subhankar et. al, 2022] that finds statistically significant regional colocation patterns. However, the numerous simultaneous statistical inferences raise the risk of false discoveries (also known as the multiple comparisons problem) and carry a high computational cost. We propose a novel algorithm, namely, multiple comparisons regional colocation miner (MultComp-RCM) which uses a Bonferroni correction. Theoretical analysis, experimental evaluation, and case study results show that the proposed method reduces both the false discovery rate and computational cost.
Cite as

Subhankar Ghosh, Jayant Gupta, Arun Sharma, Shuai An, and Shashi Shekhar. Reducing False Discoveries in Statistically-Significant Regional-Colocation Mining: A Summary of Results. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.GIScience.2023.3,
  author =	{Ghosh, Subhankar and Gupta, Jayant and Sharma, Arun and An, Shuai and Shekhar, Shashi},
  title =	{{Reducing False Discoveries in Statistically-Significant Regional-Colocation Mining: A Summary of Results}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.3},
  URN =		{urn:nbn:de:0030-drops-188985},
  doi =		{10.4230/LIPIcs.GIScience.2023.3},
  annote =	{Keywords: Colocation pattern, Participation index, Multiple comparisons problem, Spatial heterogeneity, Statistical significance}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2022.26
Abnormal Trajectory-Gap Detection: A Summary (Short Paper)

Authors: Arun Sharma, Jayant Gupta, and Shashi Shekhar

Published in: LIPIcs, Volume 240, 15th International Conference on Spatial Information Theory (COSIT 2022)

Abstract
Given trajectories with gaps (i.e., missing data), we investigate algorithms to identify abnormal gaps for testing possible hypotheses of anomalous regions. Here, an abnormal gap within a trajectory is defined as an area where a given moving object did not report its location, but other moving objects did periodically. The problem is important due to its societal applications, such as improving maritime safety and regulatory enforcement for global security concerns such as illegal fishing, illegal oil transfer, and trans-shipments. The problem is challenging due to the difficulty of interpreting missing data within a trajectory gap, and the high computational cost of detecting gaps in such a large volume of location data proves computationally very expensive. The current literature assumes linear interpolation within gaps, which may not be able to detect abnormal gaps since objects within a given region may have traveled away from their shortest path. To overcome this limitation, we propose an abnormal gap detection (AGD) algorithm that leverages the concepts of a space-time prism model where we assume space-time interpolation. We then propose a refined memoized abnormal gap detection (Memo-AGD) algorithm that reduces comparison operations. We validated both algorithms using synthetic and real-world data. The results show that abnormal gaps detected by our algorithms give better estimates of abnormality than linear interpolation and can be used for further investigation from the human analysts.
Cite as

Arun Sharma, Jayant Gupta, and Shashi Shekhar. Abnormal Trajectory-Gap Detection: A Summary (Short Paper). In 15th International Conference on Spatial Information Theory (COSIT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 240, pp. 26:1-26:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sharma_et_al:LIPIcs.COSIT.2022.26,
  author =	{Sharma, Arun and Gupta, Jayant and Shekhar, Shashi},
  title =	{{Abnormal Trajectory-Gap Detection: A Summary}},
  booktitle =	{15th International Conference on Spatial Information Theory (COSIT 2022)},
  pages =	{26:1--26:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-257-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{240},
  editor =	{Ishikawa, Toru and Fabrikant, Sara Irina and Winter, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2022.26},
  URN =		{urn:nbn:de:0030-drops-169115},
  doi =		{10.4230/LIPIcs.COSIT.2022.26},
  annote =	{Keywords: Spatial Data Mining, Trajectory Mining, Time Geography}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.13
Analyzing Trajectory Gaps for Possible Rendezvous: A Summary of Results

Authors: Arun Sharma, Xun Tang, Jayant Gupta, Majid Farhadloo, and Shashi Shekhar

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
Given trajectory data with gaps, we investigate methods to identify possible rendezvous regions. Societal applications include improving maritime safety and regulations. The challenges come from two aspects. If trajectory data are not available around the rendezvous then either linear or shortest-path interpolation may fail to detect the possible rendezvous. Furthermore, the problem is computationally expensive due to the large number of gaps and associated trajectories. In this paper, we first use the plane sweep algorithm as a baseline. Then we propose a new filtering framework using the concept of a space-time grid. Experimental results and case study on real-world maritime trajectory data show that the proposed approach substantially improves the Area Pruning Efficiency over the baseline technique.
Cite as

Arun Sharma, Xun Tang, Jayant Gupta, Majid Farhadloo, and Shashi Shekhar. Analyzing Trajectory Gaps for Possible Rendezvous: A Summary of Results. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sharma_et_al:LIPIcs.GIScience.2021.I.13,
  author =	{Sharma, Arun and Tang, Xun and Gupta, Jayant and Farhadloo, Majid and Shekhar, Shashi},
  title =	{{Analyzing Trajectory Gaps for Possible Rendezvous: A Summary of Results}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.13},
  URN =		{urn:nbn:de:0030-drops-130482},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.13},
  annote =	{Keywords: Spatial data mining, trajectory mining, time geography}
}
Document
DOI: 10.4230/LIPIcs.GISCIENCE.2018.10
Local Co-location Pattern Detection: A Summary of Results

Authors: Yan Li and Shashi Shekhar

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Given a set of spatial objects of different features (e.g., mall, hospital) and a spatial relation (e.g., geographic proximity), the problem of local co-location pattern detection (LCPD) pairs co-location patterns and localities such that the co-location patterns tend to exist inside the paired localities. A co-location pattern is a set of spatial features, the objects of which are often related to each other. Local co-location patterns are common in many fields, such as public security, and public health. For example, assault crimes and drunk driving events co-locate near bars. The problem is computationally challenging because of the exponential number of potential co-location patterns and candidate localities. The related work applies data-unaware or clustering heuristics to partition the study area, which results in incomplete enumeration of possible localities. In this study, we formally defined the LCPD problem where the candidate locality was defined using minimum orthogonal bounding rectangles (MOBRs). Then, we proposed a Quadruplet & Grid Filter-Refine (QGFR) algorithm that leveraged an MOBR enumeration lemma, and a novel upper bound on the participation index to efficiently prune the search space. The experimental evaluation showed that the QGFR algorithm reduced the computation cost substantially. One case study using the North American Atlas-Hydrography and U.S. Major City Datasets was conducted to discover local co-location patterns which would be missed if the entire dataset was analyzed or methods proposed by the related work were applied.
Cite as

Yan Li and Shashi Shekhar. Local Co-location Pattern Detection: A Summary of Results. In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.GISCIENCE.2018.10,
  author =	{Li, Yan and Shekhar, Shashi},
  title =	{{Local Co-location Pattern Detection: A Summary of Results}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.10},
  URN =		{urn:nbn:de:0030-drops-93387},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.10},
  annote =	{Keywords: Co-location pattern, Participation index, Spatial heterogeneity}
}
Document
DOI: 10.4230/DagSemProc.10121.3
Capacity Constrained Routing Algorithms for Evacuation Route Planning

Authors: Shashi Shekhar, Betsy George, and Qingsong Lu

Published in: Dagstuhl Seminar Proceedings, Volume 10121, Computational Transportation Science (2010)

Abstract
Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in face of natural disasters or terrorist attacks. Challenges arise due to violation of key assumptions (e.g. stationary ranking of alternative routes, Wardrop equilibrium) behind popular shortest path algorithms (e.g. Dijktra's, A*) and microscopic traffic simulators (e.g. DYNASMART). Time-expanded graphs (TEG) based mathematical programming paradigm does not scale up to large urban scenarios due to excessive duplication of transportation network across time-points. We present a new approach, namely Capacity Constrained Route Planner (CCRP), advancing ideas such as Time-Aggregated Graph (TAG) and an ATST function to provide earliest-Arrival-Time given any Start-Time. Laboratory experiments and field use in Twincities for DHS scenarios (e.g. Nuclear power plant, terrorism) show that CCRP is much faster than the state of the art. A key Transportation Science insight suggests that walking the first mile, when appropriate, may speed-up evacuation by a factor of 2 to 3 for many scenarios. Geographic Information Science (e.g. Time Geography) contributions include a novel representation (e.g. TAG) for spatio-temporal networks. Computer Science contributions include graph theory limitations (e.g. non-stationary ranking of routes, non-FIFO behavior) and scalable algorithms for traditional routing problems in time-varying networks, as well as new problems such as identifying the best start-time (for a given arrival-time deadline) to minimize travel-time.
Cite as

Shashi Shekhar, Betsy George, and Qingsong Lu. Capacity Constrained Routing Algorithms for Evacuation Route Planning. In Computational Transportation Science. Dagstuhl Seminar Proceedings, Volume 10121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{shekhar_et_al:DagSemProc.10121.3,
  author =	{Shekhar, Shashi and George, Betsy and Lu, Qingsong},
  title =	{{Capacity Constrained Routing Algorithms for Evacuation Route Planning}},
  booktitle =	{Computational Transportation Science},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10121},
  editor =	{Glenn Geers and Monika Sester and Stephan Winter and Ouri E. Wolfson},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10121.3},
  URN =		{urn:nbn:de:0030-drops-27216},
  doi =		{10.4230/DagSemProc.10121.3},
  annote =	{Keywords: Evacuation, routes, spatio-temporal networks}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact