Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 5 of 5
Full-Text Articles in Physical Sciences and Mathematics
Scalable Structural Index Construction For Json Analytics, Lin Jiang, Junqiao Qiu, Zhijia Zhao
Scalable Structural Index Construction For Json Analytics, Lin Jiang, Junqiao Qiu, Zhijia Zhao
Michigan Tech Publications
JavaScript Object Notation ( JSON) and its variants have gained great popularity in recent years. Unfortunately, the performance of their analytics is often dragged down by the expensive JSON parsing. To address this, recent work has shown that building bitwise indices on JSON data, called structural indices, can greatly accelerate querying. Despite its promise, the existing structural index construction does not scale well as records become larger and more complex, due to its (inherently) sequential construction process and the involvement of costly memory copies that grow as the nesting level increases. To address the above issues, this work introduces Pison …
Text Indexing And Searching In Sublinear Time, J. Ian Munro, Gonzalo Navarro, Yakov Nekrich
Text Indexing And Searching In Sublinear Time, J. Ian Munro, Gonzalo Navarro, Yakov Nekrich
Michigan Tech Publications
We introduce the first index that can be built in o(n) time for a text of length n, and can also be queried in o(q) time for a pattern of length q. On an alphabet of size, our index uses O(n log) bits, is built in O(n log f/plog n) deterministic time, and computes the number of occurrences of the pattern in time O(q/logf n+log n logf n). Each such occurrence can then be found in O(log n) time. Other trade-offs between the space usage and the cost of reporting occurrences are also possible. 2012 ACM Subject Classification Theory of …
Machine Learning For The Preliminary Diagnosis Of Dementia, Fubao Zhu, Xiaonan Li, Haipeng Tang, Zhuo He, Chaoyang Zhang, Guang-Uei Hung, Pai-Yi Chiu, Weihua Zhou
Machine Learning For The Preliminary Diagnosis Of Dementia, Fubao Zhu, Xiaonan Li, Haipeng Tang, Zhuo He, Chaoyang Zhang, Guang-Uei Hung, Pai-Yi Chiu, Weihua Zhou
Michigan Tech Publications
Objective. The reliable diagnosis remains a challenging issue in the early stages of dementia. We aimed to develop and validate a new method based on machine learning to help the preliminary diagnosis of normal, mild cognitive impairment (MCI), very mild dementia (VMD), and dementia using an informant-based questionnaire. Methods. We enrolled 5,272 individuals who filled out a 37-item questionnaire. In order to select the most important features, three different techniques of feature selection were tested. Then, the top features combined with six classification algorithms were used to develop the diagnostic models. Results. Information Gain was the most …
Fast Preprocessing For Optimal Orthogonal Range Reporting And Range Successor With Applications To Text Indexing, Younan Gao, Meng He, Yakov Nekrich
Fast Preprocessing For Optimal Orthogonal Range Reporting And Range Successor With Applications To Text Indexing, Younan Gao, Meng He, Yakov Nekrich
Michigan Tech Publications
Under the word RAM model, we design three data structures that can be constructed in O(n√lg n) time over n points in an n×n grid. The first data structure is an O(n lg n)-word structure supporting orthogonal range reporting in O(lg lg n + k) time, where k denotes output size and is an arbitrarily small constant. The second is an O(n lg lg n)-word structure supporting orthogonal range successor in O(lg lg n) time, while the third is an O(n lg n)-word structure supporting sorted range reporting in O(lg lg n + k) time. The query times of these …
Distance Oracles For Interval Graphs Via Breadth-First Rank/Select In Succinct Trees, Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, Kaiyu Wu
Distance Oracles For Interval Graphs Via Breadth-First Rank/Select In Succinct Trees, Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, Kaiyu Wu
Michigan Tech Publications
We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports the mapping between preorder (i.e., depth-first) ranks and level-order (breadth-first) ranks of nodes in constant time. Our distance oracles for interval graphs also support navigation queries – testing adjacency, computing node degrees, neighborhoods, and shortest paths – all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well …