Source author record

Matthew Skala

Matthew Skala appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Computation and Language Computational Geometry Data Structures and Algorithms Databases math.PR stat.OT

Catalog footprint

What is connected

6works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Approximate Furthest Neighbor with Application to Annulus Query

Much recent work has been devoted to approximate nearest neighbor queries. Motivated by applications in recommender systems, we consider approximate furthest neighbor (AFN) queries and present a simple, fast, and highly practical data structure for answering AFN queries in high- dimensional Euclidean space. The method builds on the technique of In- dyk (SODA 2003), storing random projections to provide sublinear query time for AFN. However, we introduce a different query algorithm, improving on Indyk's approximation factor and reducing the running time by a logarithmic factor. We also present a variation based on a query- independent ordering of the database points; while this does not have the provable approximation factor of the query-dependent data structure, it offers significant improvement in time and space complexity. We give a theoretical analysis, and experimental results. As an application, the query-dependent approach is used for deriving a data structure for the approximate annulus query problem, which is defined as follows: given an input set S and two parameters r > 0 and w >= 1, construct a data structure that returns for each query point q a point p in S such that the distance between p and q is at least r/w and at most wr.

preprint2016arXiv

Graph Nimors

In the game of Graph Nimors, two players alternately perform graph minor operations (deletion and contraction of edges) on a graph until no edges remain, at which point the player who last moved wins. We present theoretical and experimental results and conjectures regarding this game.

preprint2014arXiv

A Structural Query System for Han Characters

The IDSgrep structural query system for Han character dictionaries is presented. This system includes a data model and syntax for describing the spatial structure of Han characters using Extended Ideographic Description Sequences (EIDSes) based on the Unicode IDS syntax; a language for querying EIDS databases, designed to suit the needs of font developers and foreign language learners; a bit vector index inspired by Bloom filters for faster query operations; a freely available implementation; and format translation from popular third-party IDS and XML character databases. Experimental results are included, with a comparison to other software used for similar applications.

preprint2014arXiv

Cycle-maximal triangle-free graphs

We conjecture that the balanced complete bipartite graph $K_{\lfloor n/2 \rfloor,\lceil n/2 \rceil}$ contains more cycles than any other $n$-vertex triangle-free graph, and we make some progress toward proving this. We give equivalent conditions for cycle-maximal triangle-free graphs; show bounds on the numbers of cycles in graphs depending on numbers of vertices and edges, girth, and homomorphisms to small fixed graphs; and use the bounds to show that among regular graphs, the conjecture holds. We also consider graphs that are close to being regular, with the minimum and maximum degrees differing by at most a positive integer $k$. For $k=1$, we show that any such counterexamples have $n\le 91$ and are not homomorphic to $C_5$; and for any fixed $k$ there exists a finite upper bound on the number of vertices in a counterexample. Finally, we describe an algorithm for efficiently computing the matrix permanent (a #P-complete problem in general) in a special case used by our bounds.

preprint2013arXiv

Hypergeometric tail inequalities: ending the insanity

The hypergeometric distribution is briefly and informally surveyed, including popular notation, symmetries, and the tail inequalities $Pr[i \ge E[i]+tn] \le e^{-2t^2n}$ and $Pr[i \le E[i]-tn] \le e^{-2t^2n}$.

preprint2012arXiv

Robust Non-Parametric Data Approximation of Pointsets via Data Reduction

In this paper we present a novel non-parametric method of simplifying piecewise linear curves and we apply this method as a statistical approximation of structure within sequential data in the plane. We consider the problem of minimizing the average length of sequences of consecutive input points that lie on any one side of the simplified curve. Specifically, given a sequence $P$ of $n$ points in the plane that determine a simple polygonal chain consisting of $n-1$ segments, we describe algorithms for selecting an ordered subset $Q \subset P$ (including the first and last points of $P$) that determines a second polygonal chain to approximate $P$, such that the number of crossings between the two polygonal chains is maximized, and the cardinality of $Q$ is minimized among all such maximizing subsets of $P$. Our algorithms have respective running times $O(n^2\log n)$ when $P$ is monotonic and $O(n^2\log^2 n)$ when $P$ is an arbitrary simple polyline. Finally, we examine the application of our algorithms iteratively in a bootstrapping technique to define a smooth robust non-parametric approximation of the original sequence.