k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation

A k nearest neighbor (kNN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.

From Word Embeddings to Item Recommendation

Social network platforms can archive data produced by their users and re-use the data to serve the users better. One of the services that these platforms provide is the recommendation service. Recommendation systems can predict the future preferences of the users using various different techniques. One of the most popular technique for recommendation is matrix-factorization, which uses low-rank approximation of input data. Similarly word embedding methods from natural language processing literature learn low-dimensional vector space representation of input elements. Noticing the similarities among word embedding and matrix factorization techniques and based on the previous works that apply techniques from text processing for recommendation, Word2Vec’s skip-gram technique is employed to make recommendations. Unlike previous works that use Word2Vec for recommendation, non-textual features are used. The aim of this work is to make recommendation on next check-in venues and a Foursquare check-in dataset is used for this purpose. The results showed that use of vector space representations of items modelled by skip-gram technique is promising for making recommendations.

Angrier Birds: Bayesian reinforcement learning

We train a reinforcement learner to play a simplified version of the game Angry Birds. The learner is provided with a game state in a manner similar to the output that could be produced by computer vision algorithms. We improve on the efficiency of regular {\epsilon}-greedy Q-Learning with linear function approximation through more systematic exploration in Randomized Least Squares Value Iteration (RLSVI), an algorithm that samples its policy from a posterior distribution on optimal policies. With larger state-action spaces, efficient exploration becomes increasingly important, as evidenced by the faster learning in RLSVI.

An Automaton Learning Approach to Solving Safety Games over Infinite Graphs

Branching Random Walks, Stable Point Processes and Regular Variation

Large Collection of Diverse Gene Set Search Queries Recapitulate Known Protein-Protein Interactions and Gene-Gene Functional Associations

Weak and Strong disorder for the stochastic heat equation and the continuous directed polymer in $d\geq 3$

Fuzzy Object-Oriented Dynamic Networks. I

Polynomial partitioning for several sets of varieties

Toward Organic Computing Approach for Cybernetic Responsive Environment

Automatic Construction of Evaluation Sets and Evaluation of Document Similarity Models in Large Scholarly Retrieval Systems

NodIO, a JavaScript framework for volunteer-based evolutionary algorithms : first results

Corrigendum to: Phase transition in equilibrium fluctuations of symmetric slowed exclusion

Modelling correlated ordinal data by random-effects logistic regression models: simulation and application

Two Lax systems for the Painlevé II equation, and two related kernels in random matrix theory

Grafalgo – A Library of Graph Algorithms and Supporting Data Structures (revised)

Compositions colored by simplicial polytopic numbers

Distributed Synthesis in Continuous Time

Duality and deformations of stable Grothendieck polynomials

Quaternion-Valued Single-Phase Model for Three-Phase Power Systems

Interacting Generalized Pólya Urn Systems

State Space representation of non-stationary Gaussian Processes

Leveraging Sentence-level Information with Encoder LSTM for Natural Language Understanding

Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

Fast decay of covariances under $δ-$pinning in the critical and supercritical membrane model

Fast Kronecker product kernel methods via sampled vec trick

A spectral-based numerical method for Kolmogorov equations in Hilbert spaces

The Expurgation-Augmentation Method for Constructing Good Plane Subspace Codes

Cumulants of Jack symmetric functions and $b$-conjecture

Advanced Cloud Privacy Threat Modeling

Security and Privacy of Sensitive Data in Cloud Computing: A Survey of Recent Developments

A note on induced Ramsey numbers

Complexity of Shift Bribery in Committee Elections

An O(m log n) Algorithm for Stuttering Equivalence and Branching Bisimulation

Fractional diffusion-type equations with exponential and logarithmic differential operators

Bootstrap uniform central limit theorems for Harris recurrent Markov chains

Tensor and Its Tucker Core: the Invariance Relationships

Maximum Leaf Spanning Trees of Growing Sierpinski Networks Models

Bayesian Inference for the Extremal Dependence

New asymptotic results in principal component analysis

Optimal Strong Approximation of the One-dimensional Squared {B}essel Process

A Bayesian Approach to Determination of Convergence,Divergence and Oscillation of Infinite Series with Application to Riemann Hypothesis

On differentiability of implicitly defined function in semi-parametric profile likelihood estimation

Unitary transformations, empirical processes and distribution free testing

Multi-model Cross Pollination in Time

Local average causal effects and superefficiency

Learning Kernels for Structured Prediction using Polynomial Kernel Transformations

Cyclability of $id$-cycles in graphs

On the Computation of the Optimal Connecting Points in Road Networks

Combinatorial aspects of the quantized universal enveloping algebra of $\mathfrak{sl}_{n+1}(\mathbb{C})$

Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs

Properties of Catlin’s reduced graphs and supereulerian graphs

A unified view of LIBOR models

Identities for partial Bell polynomials derived from identities for weighted integer compositions

Bayesian Non-Negative Matrix Factorization

Joint Learning of the Embedding of Words and Entities for Named Entity Disambiguation

Using a new zero forcing process to guarantee the Strong Arnold Property

A Serial Multilevel Hypergraph Partitioning Algorithm

Quantitative scaling of magnetic avalanches

Extremal eternal multiplicative coalescent is encoded by its L{é}vy-type processes