An official website of the United States government
Themonotone minimal perfect hash function(MMPHF)problem is the following indexing problem. Given a set\(S=\{s_{1},\ldots,s_{n}\}\)of\(n\)distinct keys from a universe\(U\)of size\(u\), create a data structure\(\mathbf{D}\)that answers the following query:\(\rm{{R\small{ANK}}}(q)=\begin{cases}\text{rank of }q\text{ in }S&q\in S \\ \text{arbitrary answer}&\text{otherwise.}\end{cases}\) Solutions to the MMPHF problem are in widespread use in both theory and practice. The best upper bound known for the problem encodes\(\mathbf{D}\)in\(O(n\log\log\log u)\)bits and performs queries in\(O(\log u)\)time. It has been an open problem to either improve the space upper bound or to show that this somewhat odd looking bound is tight. In this article, we show the latter: any data structure (deterministic or randomized) for monotone minimal perfect hashing of any collection of\(n\)elements from a universe of size\(u\)requires\(\Omega(n\cdot\log\log\log{u})\)expected bits to answer every query correctly. We achieve our lower bound by defining a graph\(\mathbf{G}\)where the nodes are the possible\({u\choose n}\)inputs and where two nodes are adjacent if they cannot share the same\(\mathbf{D}\). The size of\(\mathbf{D}\)is then lower bounded by the log of the chromatic number of\(\mathbf{G}\). Finally, we show that the fractional chromatic number (and hence the chromatic number) of\(\mathbf{G}\)is lower bounded by\(2^{\Omega(n\log\log\log u)}\).
more »
« less
Towards Recognizing Food Types for Unseen Subjects
Recognizing food types through sensor signals for unseen users remains remarkably challenging, despite extensive recent studies. The efficacy of prior machine learning techniques is dwarfed by giant variations of data collected from multiple participants, partly because users have varied chewing habits and wear sensor devices in various manners. This work treats the problem as an instance of the domain adaptation problem, where each user represents a domain. We develop the first multi-source domain adaptation (MSDA) method for food-typing recognition, which consists of three major components: stratified normalization, a multi-source domain adaptor, and adaptive ensemble learning. New techniques are developed for each component. Using a real-world dataset comprised of 15 participants, we demonstrate that our method achieves\(1.33\times\)to\(2.13\times\)improvement in accuracy compared with nine state-of-the-art MSDA baselines. Additionally, we perform an in-depth ablation study to examine the behavior of each component and confirm their efficacy.
more »
« less
- PAR ID:
- 10559639
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- ACM Transactions on Computing for Healthcare
- ISSN:
- 2637-8051
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Given a weighted, ordered query set\(Q\)and a partition of\(Q\)into classes, we study the problem of computing a minimum-cost decision tree that, given any query\(q\in Q\), uses equality tests and less-than tests to determine\(q\)'s class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify\(q\), not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.more » « less
-
This paper introduces a new data-structural object that we call the tiny pointer. In many applications, traditional\(\log n\)-bit pointers can be replaced with\(o(\log n)\)-bit tiny pointers at the cost of only a constant-factor time overhead and a small probability of failure. We develop a comprehensive theory of tiny pointers, and give optimal constructions for both fixed-size tiny pointers (i.e., settings in which all of the tiny pointers must be the same size) and variable-size tiny pointers (i.e., settings in which the average tiny-pointer size must be small, but some tiny pointers can be larger). If a tiny pointer references an item in an array filled to load factor\(1-\delta\), then the optimal tiny-pointer size is\(\Theta(\log\log\log n+\log\delta^{-1})\)bits in the fixed-size case, and\(\Theta(\log\delta^{-1})\)expected bits in the variable-size case. Our tiny-pointer constructions also require us to revisit several classic problems having to do with balls and bins; these results may be of independent interest. Using tiny pointers, we apply tiny pointers to five classic data-structure problems. We show that:A data structure storing\(n\)\(v\)-bit values for\(n\)keys with constant-factor time modifications/queries can be implemented to take space\(nv+O(n\log^{(r)}n)\)bits, for any constant\(r\gt0\), as long as the user stores a tiny pointer of expected size\(O(1)\)with each key—here,\(\log^{(r)}n\)is the\(r\)-th iterated logarithm.Any binary search tree can be made succinct, meaning that it achieves\((1+o(1))\)times the optimal space, with constant-factor time overhead, and can even be made to be within\(O(n)\)bits of optimal if we allow for\(O(\log^{*}n)\)-time modifications—this holds even for rotation-based trees such as the splay tree and the red-black tree.Any fixed-capacity key-value dictionary can be made stable (i.e., items do not move once inserted) with constant-factor time overhead and\((1+o(1))\)-factor space overhead.Any key-value dictionary that requires uniform-size values can be made to support arbitrary-size values with constant-factor time overhead and with an additional space consumption of\(\log^{(r)}n+O(\log j)\)bits per\(j\)-bit value for an arbitrary constant\(r\gt0\)of our choice.Given an external-memory array\(A\)of size\((1+\varepsilon)n\)containing a dynamic set of up to\(n\)key-value pairs, it is possible to maintain an internal-memory stash of size\(O(n\log\varepsilon^{-1})\)bits so that the location of any key-value pair in\(A\)can be computed in constant time (and with no IOs). In each case tiny pointers allow for us to take a natural space-inefficient solution that uses pointers and make it space-efficient for free.more » « less
-
The metric\(k\)-median problem is a classical and widely studied objective for data clustering, with applications in data analysis, computer vision, genomics, and facility location. The current best approximation algorithms for\(k\)-median rely on first obtaining a structured fractional solution known as abi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-discretized partitioning schemes for the facilities, along with corresponding sets of randomized algorithms and factor-revealing non-linear programs. We show this hierarchy improves upon the current best factor of\(1.3371\), proving that the third layer of this hierarchy achieves a rounding factor of\(1.3064\), while no layer can achieve a factor smaller than\(1.2943\)in expectation. Combined with the current best algorithm for bi-point solution generation, we get a\(2.6081\)approximation factor for\(k\)-median. On the negative side, we give a family of bi-point solutions with integrality gap approaching the square root of the golden ratio, approximately\(1.272\), even when allowed to open\(k+o(k)\)facilities. Altogether, our results substantially narrow the approximation gap for bi-point solutions.more » « less
-
Stream processing, which involves real-time computation of data as it is created or received, is vital for various applications, specifically wireless communication. The evolving protocols, the requirement for high-throughput, and the challenges of handling diverse processing patterns make it demanding. Traditional platforms grapple with meeting real-time throughput and latency requirements due to large data volume, sequential and indeterministic data arrival, and variable data rates, leading to inefficiencies in memory access and parallel processing. We present Canalis, a throughput-optimized framework designed to address these challenges, ensuring high-performance while achieving low energy consumption. Canalis is a hardware-software co-designed system. It includes a programmable spatial architecture, Flux Stream Processing Unit (FluxSPU), proposed by this work to enhance data throughput and energy efficiency. FluxSPU is accompanied by a software stack that eases the programming process. We evaluated Canalis with eight distinct benchmarks. When compared to CPU and GPU in mobile SoC to demonstrate the effectiveness of domain specialization, Canalis achieves an average speedup of 13.4\(\times\)and 6.6\(\times\), and energy savings of 189.8\(\times\)and 283.9\(\times\), respectively. In contrast to equivalent ASICs of the benchmarks, the average energy overhead of Canalis is within 2.4\(\times\), successfully maintaining generalizations without incurring significant overhead.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1145/3696424
