Data Structures And Algorithms
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs (1804.03485v3)
Parinya Chalermsook, Andreas Schmid, Sumedha Uniyal
2018-04-10
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph
contains a cactus subgraph where contains at least a fraction of the triangular faces of . We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A approximation algorithm for, given any graph , finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous -approximation; (ii) An alternate (and arguably more illustrative) proof of the approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
Dynamic Planar Point Location in External Memory (1903.06601v1)
J. Ian Munro, Yakov Nekrich
2019-03-15
In this paper we describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in
I/Os and updates in amortized I/Os, where is the number of segments in the subdivision and is the block size. This is the first dynamic data structure with almost-optimal query cost. For comparison all previously known results for this problem require I/Os to answer queries. Our result almost matches the best known upper bound in the internal-memory model.
Proportionally dense subgraph of maximum size: complexity and approximation (1903.06579v1)
Janka Chlebíková, Cristina Bazgan, Clément Dallard, Thomas Pontoizeau
2019-03-15
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time
-approximation algorithm for the problem, where is the maximum degree of the graph. Finally, we prove that all Hamiltonian cubic graphs (except two) have a PDS of the maximum possible size which can be found in linear time if a Hamiltonian cycle is given in input.
scaleBF: A High Scalable Membership Filter using 3D Bloom Filter (1903.06570v1)
Ripon Patgiri, Sabuzima Nayak, Samir Kumar Borgohain
2019-03-15
Bloom Filter is extensively deployed data structure in various applications and research domain since its inception. Bloom Filter is able to reduce the space consumption in an order of magnitude. Thus, Bloom Filter is used to keep information of a very large scale data. There are numerous variants of Bloom Filters available, however, scalability is a serious dilemma of Bloom Filter for years. To solve this dilemma, there are also diverse variants of Bloom Filter. However, the time complexity and space complexity become the key issue again. In this paper, we present a novel Bloom Filter to address the scalability issue without compromising the performance, called scaleBF. scaleBF deploys many 3D Bloom Filter to filter the set of items. In this paper, we theoretically compare the contemporary Bloom Filter for scalability and scaleBF outperforms in terms of time complexity.
A Faster Algorithm Enumerating Relevant Features over Finite Fields (1903.06412v1)
Mikito Nanashima
2019-03-15
A
-junta function is a function which depends on only coordinates of the input. For relatively small w.r.t. the input size , learning -junta functions is one of fundamental problems both theoretically and practically in machine learning. For the last two decades, much effort has been made to design efficient learning algorithms for Boolean junta functions, and some novel techniques have been developed. However, in real world, multi-labeled data seem to be obtained in much more often than binary-labeled one. Thus, it is a natural question whether these techniques can be applied to more general cases about the alphabet size. In this paper, we expand the Fourier detection techniques for the binary alphabet to any finite field , and give, roughly speaking, an -time learning algorithm for -juntas over . Note that our algorithm is the first non-trivial (i.e., non-brute force) algorithm for such a class even in the case where and we give an affirmative answer to the question posed in [MOS04]. Our algorithm consists of two reductions: (1) from learning juntas to LDME which is a variant of the learning with errors (LWE) problems introduced by [Reg05], and (2) from LDME to the light bulb problem (LBP) introduced by [Val88]. Since the reduced problem (i.e., LBP) is a kind of binary problem regardless of the alphabet size of the original problem (i.e., learning juntas), we can directly apply the techniques for the binary case in the previous work such as in [Val15, KKK18].
Deterministic Approximation of Random Walks in Small Space (1903.06361v1)
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil Vadhan
2019-03-15
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph
, a positive integer , and a set of vertices, approximates the conductance of in the -step random walk on to within a factor of , where is an arbitrarily small constant. More generally, our algorithm computes an -spectral approximation to the normalized Laplacian of the -step walk. Our algorithm combines the derandomized square graph operation (Rozenman and Vadhan, 2005), which we recently used for solving Laplacian systems in nearly logarithmic space (Murtagh, Reingold, Sidford, and Vadhan, 2017), with ideas from (Cheng, Cheng, Liu, Peng, and Teng, 2015), which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even (while ours works for all ). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd . Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.
Subset Selection for Matrices with Fixed Blocks (1903.06350v1)
Jiaxin Xie, Zhiqiang Xu
2019-03-15
Subset selection for matrices is the task of extracting a column sub-matrix from a given matrix
with such that the pseudoinverse of the sampled matrix has as small Frobenius or spectral norm as possible. In this paper, we consider the more general problem of subset selection for matrices that allows a block is fixed at the beginning. Under this setting, we provide a deterministic method for selecting a column sub-matrix from . We also present a bound for both the Frobenius and the spectral matrix norms of the pseudoinverse of the sampled matrix with showing that the bound is asymptotically optimal. The main technology for proving this result is the interlacing families of polynomials which is developed by Marcus, Spielman and Srivastava. This idea also results in a deterministic greedy selection algorithm that produces the sub-matrix promised by our result.
Utility Preserving Secure Private Data Release (1901.09858v3)
Jasjeet Dhaliwal, Geoffrey So, Aleatha Parker-Wood, Melanie Beck
2019-01-28
Differential privacy mechanisms that also make reconstruction of the data impossible come at a cost - a decrease in utility. In this paper, we tackle this problem by designing a private data release mechanism that makes reconstruction of the original data impossible and also preserves utility for a wide range of machine learning algorithms. We do so by combining the Johnson-Lindenstrauss (JL) transform with noise generated from a Laplace distribution. While the JL transform can itself provide privacy guarantees \cite{blocki2012johnson} and make reconstruction impossible, we do not rely on its differential privacy properties and only utilize its ability to make reconstruction impossible. We present novel proofs to show that our mechanism is differentially private under single element changes as well as single row changes to any database. In order to show utility, we prove that our mechanism maintains pairwise distances between points in expectation and also show that its variance is proportional to the dimensionality of the subspace we project the data into. Finally, we experimentally show the utility of our mechanism by deploying it on the task of clustering.
To Index or Not to Index: Optimizing Exact Maximum Inner Product Search (1706.01449v3)
Firas Abuzaid, Geet Sethi, Peter Bailis, Matei Zaharia
2017-06-05
Exact Maximum Inner Product Search (MIPS) is an important task that is widely pertinent to recommender systems and high-dimensional similarity search. The brute-force approach to solving exact MIPS is computationally expensive, thus spurring recent development of novel indexes and pruning techniques for this task. In this paper, we show that a hardware-efficient brute-force approach, blocked matrix multiply (BMM), can outperform the state-of-the-art MIPS solvers by over an order of magnitude, for some -- but not all -- inputs. In this paper, we also present a novel MIPS solution, MAXIMUS, that takes advantage of hardware efficiency and pruning of the search space. Like BMM, MAXIMUS is faster than other solvers by up to an order of magnitude, but again only for some inputs. Since no single solution offers the best runtime performance for all inputs, we introduce a new data-dependent optimizer, OPTIMUS, that selects online with minimal overhead the best MIPS solver for a given input. Together, OPTIMUS and MAXIMUS outperform state-of-the-art MIPS solvers by 3.2
on average, and up to 10.9 , on widely studied MIPS datasets.
Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings (1903.06290v1)
Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
2019-03-14
For a string
, a palindromic substring is said to be a shortest unique palindromic substring (SUPS) for an interval in , if occurs exactly once in , the interval contains , and every palindromic substring containing which is shorter than occurs at least twice in . In this paper, we study the problem of answering queries on run-length encoded strings. We show how to preprocess a given run-length encoded string of size in space and time so that all for any subsequent query interval can be answered in time, where is the number of outputs, and is the number of distinct runs of .