OpenRaiser/Intern-Atlas huggingface dataset:
OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks
Venue: arXiv cs.SI 2017
Year: 2017

Urban scholars have studied street networks in various ways, but there are data availability and consistency limitations to the current urban planning/street network analysis literature. To address these challenges, this article presents OSMnx, a new tool to make the collection of data and creation and analysis of street networks simple, consistent, automatable and sound from the perspectives of graph theory, transportation, and urban design. OSMnx contributes five significant capabilities for researchers and practitioners: first, the automated downloading of political boundaries and building footprints; second, the tailored and automated downloading and constructing of street network data from OpenStreetMap; third, the algorithmic correction of network topology; fourth, the ability to save street networks to disk as shapefiles, GraphML, or SVG files; and fifth, the ability to analyze street networks, including calculating routes, projecting and visualizing networks, and calculating metric and topological measures. These measures include those common in urban design and transportation studies, as well as advanced measures of the structure and topology of the network. Finally, this article presents a simple case study using OSMnx to construct and analyze street networks in Portland, Oregon.
Hamiltonian operator for spectral shape analysis
Venue: arXiv cs.GR 2017
Year: 2017

Many shape analysis methods treat the geometry of an object as a metric space that can be captured by the Laplace-Beltrami operator. In this paper, we propose to adapt the classical Hamiltonian operator from quantum mechanics to the field of shape analysis. To this end we study the addition of a potential function to the Laplacian as a generator for dual spaces in which shape processing is performed. We present a general optimization approach for solving variational problems involving the basis defined by the Hamiltonian using perturbation theory for its eigenvectors. The suggested operator is shown to produce better functional spaces to operate with, as demonstrated on different shape analysis tasks.
Adopting the FAB-MAP algorithm for indoor localization with WiFi fingerprints
Venue: arXiv cs.RO 2017
Year: 2017

Personal indoor localization is usually accomplished by fusing information from various sensors. A common choice is to use the WiFi adapter that provides information about Access Points that can be found in the vicinity. Unfortunately, state-of-the-art approaches to WiFi-based localization often employ very dense maps of the WiFi signal distribution, and require a time-consuming process of parameter selection. On the other hand, camera images are commonly used for visual place recognition, detecting whenever the user observes a scene similar to the one already recorded in a database. Visual place recognition algorithms can work with sparse databases of recorded scenes and are in general simple to parametrize. Therefore, we propose a WiFi-based global localization method employing the structure of the well-known FAB-MAP visual place recognition algorithm. Similarly to FAB-MAP our method uses Chow-Liu trees to estimate a joint probability distribution of re-observation of a place given a set of features extracted at places visited so far. However, we are the first who apply this idea to recorded WiFi scans instead of visual words. The new method is evaluated on the UJIIndoorLoc dataset used in the EvAAL competition, allowing fair comparison with other solutions.
Fingerprinting OpenFlow controllers: The first step to attack an SDN control plane
Venue: arXiv cs.NI 2017
Year: 2017

Software-Defined Networking (SDN) controllers are considered as Network Operating Systems (NOSs) and often viewed as a single point of failure. Detecting which SDN controller is managing a target network is a big step for an attacker to launch specific/effective attacks against it. In this paper, we demonstrate the feasibility of fingerpirinting SDN controllers. We propose techniques allowing an attacker placed in the data plane, which is supposed to be physically separate from the control plane, to detect which controller is managing the network. To the best of our knowledge, this is the first work on fingerprinting SDN controllers, with as primary goal to emphasize the necessity to highly secure the controller. We focus on OpenFlow-based SDN networks since OpenFlow is currently the most deployed SDN technology by hardware and software vendors.
GSM based CommSense system to measure and estimate environmental changes
Venue: arXiv cs.OH 2017
Year: 2017

Facilitating the coexistence of radar systems with communication systems has been a major area of research in radar engineering. The current work presents a new way to sense the environment using the channel equalization block of existing communication systems. We have named this system CommSense. In the current paper we demonstrate the feasibility of the system using Global System for Mobile Communications (GSM) signals. The implementation has been done using open-source Software Defined Radio (SDR) environment. In the preliminary results obtained in our work we show that it is possible to distinguish environmental changes using the proposed system. The major advantage of the system is that it is inexpensive as channel estimation is an inherent block in any communication system and hence the added cost to make it work as an environment sensor is minimal. The major challenge, on which we are continuing our work, is how to characterize the features in the environmental changes. This is an acute challenge given the fact that the bandwidth available is narrow and the system is inherently a forward looking radar. However the initial results, as shown in this paper, are encouraging and we intend to use an application specific instrumentation (ASIN) scheme to distinguish the environmental changes.
Bandwidth Enhancement in Multimode Polymer Waveguides Using Waveguide Layout for Optical Printed Circuit Boards
Venue: arXiv cs.ET 2017
Year: 2017

Dispersion studies demonstrate that waveguide layout can be used to enhance the bandwidth performance of multimode polymer waveguides for use in board-level optical interconnects, providing >40 GHzxm without the need for any launch conditioning.
Robust Cardiac Motion Estimation using Ultrafast Ultrasound Data: A Low-Rank-Topology-Preserving Approach
Venue: arXiv cs.CV 2017
Year: 2017

Cardiac motion estimation is an important diagnostic tool to detect heart diseases and it has been explored with modalities such as MRI and conventional ultrasound (US) sequences. US cardiac motion estimation still presents challenges because of the complex motion patterns and the presence of noise. In this work, we propose a novel approach to estimate the cardiac motion using ultrafast ultrasound data. -- Our solution is based on a variational formulation characterized by the L2-regularized class. The displacement is represented by a lattice of b-splines and we ensure robustness by applying a maximum likelihood type estimator. While this is an important part of our solution, the main highlight of this paper is to combine a low-rank data representation with topology preservation. Low-rank data representation (achieved by finding the k-dominant singular values of a Casorati Matrix arranged from the data sequence) speeds up the global solution and achieves noise reduction. On the other hand, topology preservation (achieved by monitoring the Jacobian determinant) allows to radically rule out distortions while carefully controlling the size of allowed expansions and contractions. Our variational approach is carried out on a realistic dataset as well as on a simulated one. We demonstrate how our proposed variational solution deals with complex deformations through careful numerical experiments. While maintaining the accuracy of the solution, the low-rank preprocessing is shown to speed up the convergence of the variational problem. Beyond cardiac motion estimation, our approach is promising for the analysis of other organs that experience motion.
A Comparison of Word Embeddings for English and Cross-Lingual Chinese Word Sense Disambiguation
Venue: arXiv cs.CL 2017
Year: 2017

Word embeddings are now ubiquitous forms of word representation in natural language processing. There have been applications of word embeddings for monolingual word sense disambiguation (WSD) in English, but few comparisons have been done. This paper attempts to bridge that gap by examining popular embeddings for the task of monolingual English WSD. Our simplified method leads to comparable state-of-the-art performance without expensive retraining. Cross-Lingual WSD - where the word senses of a word in a source language e come from a separate target translation language f - can also assist in language learning; for example, when providing translations of target vocabulary for learners. Thus we have also applied word embeddings to the novel task of cross-lingual WSD for Chinese and provide a public dataset for further benchmarking. We have also experimented with using word embeddings for LSTM networks and found surprisingly that a basic LSTM network does not work well. We discuss the ramifications of this outcome.
Bio-Inspired Spiking Convolutional Neural Network using Layer-wise Sparse Coding and STDP Learning
Venue: arXiv cs.NE 2017
Year: 2017

Hierarchical feature discovery using non-spiking convolutional neural networks (CNNs) has attracted much recent interest in machine learning and computer vision. However, it is still not well understood how to create a biologically plausible network of brain-like, spiking neurons with multi-layer, unsupervised learning. This paper explores a novel bio-inspired spiking CNN that is trained in a greedy, layer-wise fashion. The proposed network consists of a spiking convolutional-pooling layer followed by a feature discovery layer extracting independent visual features. Kernels for the convolutional layer are trained using local learning. The learning is implemented using a sparse, spiking auto-encoder representing primary visual features. The feature discovery layer extracts independent features by probabilistic, leaky integrate-and-fire (LIF) neurons that are sparsely active in response to stimuli. The layer of the probabilistic, LIF neurons implicitly provides lateral inhibitions to extract sparse and independent features. Experimental results show that the convolutional layer is stack-admissible, enabling it to support a multi-layer learning. The visual features obtained from the proposed probabilistic LIF neurons in the feature discovery layer are utilized for training a classifier. Classification results contribute to the independent and informative visual features extracted in a hierarchy of convolutional and feature discovery layers. The proposed model is evaluated on the MNIST digit dataset using clean and noisy images. The recognition performance for clean images is above 98%. The performance loss for recognizing the noisy images is in the range 0.1% to 8.5% depending on noise types and densities. This level of performance loss indicates that the network is robust to additive noise.
Learning to Play Guess Who? and Inventing a Grounded Language as a Consequence
Venue: arXiv cs.AI 2017
Year: 2017

Acquiring your first language is an incredible feat and not easily duplicated. Learning to communicate using nothing but a few pictureless books, a corpus, would likely be impossible even for humans. Nevertheless, this is the dominating approach in most natural language processing today. As an alternative, we propose the use of situated interactions between agents as a driving force for communication, and the framework of Deep Recurrent Q-Networks for evolving a shared language grounded in the provided environment. We task the agents with interactive image search in the form of the game Guess Who?. The images from the game provide a non trivial environment for the agents to discuss and a natural grounding for the concepts they decide to encode in their communication. Our experiments show that the agents learn not only to encode physical concepts in their words, i.e. grounding, but also that the agents learn to hold a multi-step dialogue remembering the state of the dialogue from step to step.
Faster Kernel Ridge Regression Using Sketching and Preconditioning
Venue: arXiv cs.NA 2017
Year: 2017

Kernel Ridge Regression (KRR) is a simple yet powerful technique for non-parametric regression whose computation amounts to solving a linear system. This system is usually dense and highly ill-conditioned. In addition, the dimensions of the matrix are the same as the number of data points, so direct methods are unrealistic for large-scale datasets. In this paper, we propose a preconditioning technique for accelerating the solution of the aforementioned linear system. The preconditioner is based on random feature maps, such as random Fourier features, which have recently emerged as a powerful technique for speeding up and scaling the training of kernel-based methods, such as kernel ridge regression, by resorting to approximations. However, random feature maps only provide crude approximations to the kernel function, so delivering state-of-the-art results by directly solving the approximated system requires the number of random features to be very large. We show that random feature maps can be much more effective in forming preconditioners, since under certain conditions a not-too-large number of random features is sufficient to yield an effective preconditioner. We empirically evaluate our method and show it is highly effective for datasets of up to one million training examples.
Numerically robust computation of circular visibility
Venue: arXiv cs.CG 2017
Year: 2017

We address the question of whether a point inside a domain bounded by a simple closed arc spline is circularly visible from a specified arc from the boundary. We provide a simple and numerically stable linear time algorithm that solves this problem. In particular, we present an easy-to-check criterion that implies that a point is not visible from a specified boundary arc.
Invertibility and Largest Eigenvalue of Symmetric Matrix Signings
Venue: arXiv cs.DM 2017
Year: 2017

The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of identifying symmetric signings of matrices with natural spectral properties. Our results are twofold: 1. We show NP-completeness for the following three problems: verifying whether a given matrix has a symmetric signing that is positive semi-definite/singular/has bounded eigenvalues. However, we also illustrate that the complexity could substantially differ for input matrices that are adjacency matrices of graphs. 2. We exhibit a stark contrast between invertibility and the above-mentioned spectral properties: we show a combinatorial characterization of matrices with invertible symmetric signings and design an efficient algorithm using this characterization to verify whether a given matrix has an invertible symmetric signing. Next, we give an efficient algorithm to solve the search problem of finding an invertible symmetric signing for matrices whose support graph is bipartite. We also provide a lower bound on the number of invertible symmetric signed adjacency matrices. Finally, we give an efficient algorithm to find a minimum increase in support of a given symmetric matrix so that it has an invertible symmetric signing. We use combinatorial and spectral techniques in addition to classic results from matching theory. Our combinatorial characterization of matrices with invertible symmetric signings might be of independent interest.
Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and $O(n^{1/2-ε})$-Time
Venue: arXiv cs.DS 2017
Year: 2017

We present two algorithms for dynamically maintaining a spanning forest of a graph undergoing edge insertions and deletions. Our algorithms guarantee {\em worst-case update time} and work against an adaptive adversary, meaning that an edge update can depend on previous outputs of the algorithms. We provide the first polynomial improvement over the long-standing $O(\sqrt{n})$ bound of [Frederickson STOC'83, Eppstein, Galil, Italiano and Nissenzweig FOCS'92] for such type of algorithms. The previously best improvement was $O(\sqrt{n (\log\log n)^2/\log n})$ [Kejlberg-Rasmussen, Kopelowitz, Pettie and Thorup ESA'16]. We note however that these bounds were obtained by deterministic algorithms while our algorithms are randomized. Our first algorithm is Monte Carlo and guarantees an $O(n^{0.4+o(1)})$ worst-case update time, where the $o(1)$ term hides the $O(\sqrt{\log\log n/\log n})$ factor. Our second algorithm is Las Vegas and guarantees an $O(n^{0.49306})$ worst-case update time with high probability. Algorithms with better update time either needed to assume that the adversary is oblivious (e.g. [Kapron, King and Mountjoy SODA'13]) or can only guarantee an amortized update time. Our second result answers an open problem by Kapron et al. To the best of our knowledge, our algorithms are among a few non-trivial randomized dynamic algorithms that work against adaptive adversaries.
When Fashion Meets Big Data: Discriminative Mining of Best Selling Clothing Features
Venue: arXiv cs.CV 2017
Year: 2017

With the prevalence of e-commence websites and the ease of online shopping, consumers are embracing huge amounts of various options in products. Undeniably, shopping is one of the most essential activities in our society and studying consumer's shopping behavior is important for the industry as well as sociology and psychology. Indisputable, one of the most popular e-commerce categories is clothing business. There arises the needs for analysis of popular and attractive clothing features which could further boost many emerging applications, such as clothing recommendation and advertising. In this work, we design a novel system that consists of three major components: 1) exploring and organizing a large-scale clothing dataset from a online shopping website, 2) pruning and extracting images of best-selling products in clothing item data and user transaction history, and 3) utilizing a machine learning based approach to discovering fine-grained clothing attributes as the representative and discriminative characteristics of popular clothing style elements. Through the experiments over a large-scale online clothing shopping dataset, we demonstrate the effectiveness of our proposed system, and obtain useful insights on clothing consumption trends and profitable clothing features.
Finite-state independence
Venue: arXiv cs.FL 2017
Year: 2017

In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. We prove that, as expected, the set of independent pairs of infinite words has Lebesgue measure 1. We show that the join of two independent normal words is normal. However, the independence of two normal words is not guaranteed if we just require that their join is normal. To prove this we construct a normal word $x_1x_2x_3\ldots$ where $x_{2n}=x_n$ for every $n$.
On Smart Query Routing: For Distributed Graph Querying with Decoupled Storage
Venue: arXiv cs.DB 2017
Year: 2017

We study online graph queries that retrieve nearby nodes of a query node from a large network. To answer such queries with high throughput and low latency, we partition the graph and process the data in parallel across a cluster of servers. State-of-the-art distributed graph querying systems place each graph partition on a separate server, where query answering over that partition takes place. This design has two major disadvantages. First, the router needs to maintain a fixed routing table. Hence, these systems are less flexible with respect to query routing, fault tolerance, and graph updates. Second, the graph data must be partitioned such that the workload across the servers is balanced, and the inter-machine communication is minimized. In addition, it is required to update the existing partitions based on workload changes over graph nodes. However, graph partitioning, online monitoring of workloads, and dynamically updating the graph partitions are expensive. In this work, we mitigate both these problems by decoupling graph storage from query processors, and by developing smart routing strategies that improve the cache locality in query processors. Since a query processor is no longer assigned any fixed part of the graph, it is equally capable of handling any request, thus facilitating load balancing and fault tolerance. On the other hand, due to our smart routing strategies, query processors can effectively leverage their cache contents, reducing the overall impact of how the graph is partitioned across storage servers. A detailed experimental evaluation with several real-world, large graph datasets demonstrates that our proposed framework, gRouting - even with simple hash partitioning of the data - achieves up to an order of magnitude better query throughput compared to existing graph querying systems that employ expensive graph partitioning and re-partitioning strategies.
Fair Public Decision Making
Venue: arXiv cs.GT 2017
Year: 2017

We generalize the classic problem of fairly allocating indivisible goods to the problem of \emph{fair public decision making}, in which a decision must be made on several social issues simultaneously, and, unlike the classic setting, a decision can provide positive utility to multiple players. We extend the popular fairness notion of proportionality (which is not guaranteeable) to our more general setting, and introduce three novel relaxations --- \emph{proportionality up to one issue, round robin share, and pessimistic proportional share} --- that are also interesting in the classic goods allocation setting. We show that the Maximum Nash Welfare solution, which is known to satisfy appealing fairness properties in the classic setting, satisfies or approximates all three relaxations in our framework. We also provide polynomial time algorithms and hardness results for finding allocations satisfying these axioms, with or without insisting on Pareto optimality.
Millimeter Wave Beam Alignment: Large Deviations Analysis and Design Insights
Venue: arXiv cs.IT 2017
Year: 2017

In millimeter wave cellular communication, fast and reliable beam alignment via beam training is crucial to harvest sufficient beamforming gain for the subsequent data transmission. In this paper, we establish fundamental limits in beam-alignment performance under both the exhaustive search and the hierarchical search that adopts multi-resolution beamforming codebooks, accounting for time-domain training overhead. Specifically, we derive lower and upper bounds on the probability of misalignment for an arbitrary level in the hierarchical search, based on a single-path channel model. Using the method of large deviations, we characterize the decay rate functions of both bounds and show that the bounds coincide as the training sequence length goes large. We go on to characterize the asymptotic misalignment probability of both the hierarchical and exhaustive search, and show that the latter asymptotically outperforms the former, subject to the same training overhead and codebook resolution. We show via numerical results that this relative performance behavior holds in the non-asymptotic regime. Moreover, the exhaustive search is shown to achieve significantly higher worst-case spectrum efficiency than the hierarchical search, when the pre-beamforming signal-to-noise ratio (SNR) is relatively low. This study hence implies that the exhaustive search is more effective for users situated further from base stations, as they tend to have low SNR.