OpenRaiser/Intern-Atlas huggingface dataset:
Local Equivalence and Intrinsic Metrics between Reeb Graphs
Venue: arXiv cs.CG 2017
Year: 2017

As graphical summaries for topological spaces and maps, Reeb graphs are common objects in the computer graphics or topological data analysis literature. Defining good metrics between these objects has become an important question for applications, where it matters to quantify the extent by which two given Reeb graphs differ. Recent contributions emphasize this aspect, proposing novel distances such as {\em functional distortion} or {\em interleaving} that are provably more discriminative than the so-called {\em bottleneck distance}, being true metrics whereas the latter is only a pseudo-metric. Their main drawback compared to the bottleneck distance is to be comparatively hard (if at all possible) to evaluate. Here we take the opposite view on the problem and show that the bottleneck distance is in fact good enough {\em locally}, in the sense that it is able to discriminate a Reeb graph from any other Reeb graph in a small enough neighborhood, as efficiently as the other metrics do. This suggests considering the {\em intrinsic metrics} induced by these distances, which turn out to be all {\em globally} equivalent. This novel viewpoint on the study of Reeb graphs has a potential impact on applications, where one may not only be interested in discriminating between data but also in interpolating between them.
Kaggle Competition: Expedia Hotel Recommendations
Venue: arXiv cs.IR 2017
Year: 2017

With hundreds, even thousands, of hotels to choose from at every destination, it's difficult to know which will suit your personal preferences. Expedia wants to take the proverbial rabbit hole out of hotel search by providing personalized hotel recommendations to their users. This is no small task for a site with hundreds of millions of visitors every month! Currently, Expedia uses search parameters to adjust their hotel recommendations, but there aren't enough customer specific data to personalize them for each user. In this project, we have taken up the challenge to contextualize customer data and predict the likelihood a user will stay at 100 different hotel groups.
Combining Bayesian Approaches and Evolutionary Techniques for the Inference of Breast Cancer Networks
Venue: arXiv cs.LG 2017
Year: 2017

Gene and protein networks are very important to model complex large-scale systems in molecular biology. Inferring or reverseengineering such networks can be defined as the process of identifying gene/protein interactions from experimental data through computational analysis. However, this task is typically complicated by the enormously large scale of the unknowns in a rather small sample size. Furthermore, when the goal is to study causal relationships within the network, tools capable of overcoming the limitations of correlation networks are required. In this work, we make use of Bayesian Graphical Models to attach this problem and, specifically, we perform a comparative study of different state-of-the-art heuristics, analyzing their performance in inferring the structure of the Bayesian Network from breast cancer data.
Quickest Visibility Queries in Polygonal Domains
Venue: arXiv cs.CG 2017
Year: 2017

Let $s$ be a point in a polygonal domain $\mathcal{P}$ of $h-1$ holes and $n$ vertices. We consider a quickest visibility query problem. Given a query point $q$ in $\mathcal{P}$, the goal is to find a shortest path in $\mathcal{P}$ to move from $s$ to see $q$ as quickly as possible. Previously, Arkin et al. (SoCG 2015) built a data structure of size $O(n^22^{α(n)}\log n)$ that can answer each query in $O(K\log^2 n)$ time, where $α(n)$ is the inverse Ackermann function and $K$ is the size of the visibility polygon of $q$ in $\mathcal{P}$ (and $K$ can be $Θ(n)$ in the worst case). In this paper, we present a new data structure of size $O(n\log h + h^2)$ that can answer each query in $O(h\log h\log n)$ time. Our result improves the previous work when $h$ is relatively small. In particular, if $h$ is a constant, then our result even matches the best result for the simple polygon case (i.e., $h=1$), which is optimal. As a by-product, we also have a new algorithm for a shortest-path-to-segment query problem. Given a query line segment $τ$ in $\mathcal{P}$, the query seeks a shortest path from $s$ to all points of $τ$. Previously, Arkin et al. gave a data structure of size $O(n^22^{α(n)}\log n)$ that can answer each query in $O(\log^2 n)$ time, and another data structure of size $O(n^3\log n)$ with $O(\log n)$ query time. We present a data structure of size $O(n)$ with query time $O(h\log \frac{n}{h})$, which also favors small values of $h$ and is optimal when $h=O(1)$.
Performance of Proportional Fair Scheduling for Downlink Non-Orthogonal Multiple Access Systems
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we present the first analytical solution for performance analysis of proportional fair scheduling (PFS) in downlink non-orthogonal multiple access (NOMA) systems. Assuming an ideal NOMA system with an arbitrary number of multiplexed users, we derive a closed-form solution of the optimal power allocation for PFS and design a low-complexity algorithm for joint power allocation and user set selection. We develop an analytical model to analyze the throughput performance of this optimal solution based on stochastic channel modeling. Our analytical performance is proved to be the upper bound for PFS and is used to estimate user data rates and overall throughput in practical NOMA systems. We conduct system-level simulations to evaluate the accuracy of our data rate estimation. The simulation results verify our analysis on the upper bound of PFS performance in NOMA and confirm that using the analytical performance for data rate estimation guarantees high accuracy. The impact of partial and imperfect channel information on the estimation performance is investigated as well.
On linear complementary-dual multinegacirculant codes
Venue: arXiv cs.IT 2017
Year: 2017

Linear codes with complementary-duals (LCD) are linear codes that intersect with their dual trivially. Multinegacirculant codes of index $2$ that are LCD are characterized algebraically and some good codes are found in this family. Exact enumeration is performed for indices 2 and 3, and for all indices $t$ for a special case of the co-index by using their concatenated structure. Asymptotic existence results are derived for the special class of such codes that are one-generator and have co-index a power of two by means of Dickson polynomials. This shows that there are infinite families of LCD multinegacirculant codes with relative distance satisfying a modified Varshamov-Gilbert bound.
ForestClaw: A parallel algorithm for patch-based adaptive mesh refinement on a forest of quadtrees
Venue: arXiv cs.MS 2017
Year: 2017

We describe a parallel, adaptive, multi-block algorithm for explicit integration of time dependent partial differential equations on two-dimensional Cartesian grids. The grid layout we consider consists of a nested hierarchy of fixed size, non-overlapping, logically Cartesian grids stored as leaves in a quadtree. Dynamic grid refinement and parallel partitioning of the grids is done through the use of the highly scalable quadtree/octree library p4est. Because our concept is multi-block, we are able to easily solve on a variety of geometries including the cubed sphere. In this paper, we pay special attention to providing details of the parallel ghost-filling algorithm needed to ensure that both corner and edge ghost regions around each grid hold valid values. We have implemented this algorithm in the ForestClaw code using single-grid solvers from ClawPack, a software package for solving hyperbolic PDEs using finite volumes methods. We show weak and strong scalability results for scalar advection problems on two-dimensional manifold domains on 1 to 64Ki MPI processes, demonstrating neglible regridding overhead.
Juggling Functions Inside a Database
Venue: arXiv cs.DB 2017
Year: 2017

We define and study the Functional Aggregate Query (FAQ) problem, which captures common computational tasks across a very wide range of domains including relational databases, logic, matrix and tensor computation, probabilistic graphical models, constraint satisfaction, and signal processing. Simply put, an FAQ is a declarative way of defining a new function from a database of input functions. We present "InsideOut", a dynamic programming algorithm, to evaluate an FAQ. The algorithm rewrites the input query into a set of easier-to-compute FAQ sub-queries. Each sub-query is then evaluated using a worst-case optimal relational join algorithm. The topic of designing algorithms to optimally evaluate the classic multiway join problem has seen exciting developments in the past few years. Our framework tightly connects these new ideas in database theory with a vast number of application areas in a coherent manner, showing potentially that a good database engine can be a general-purpose constraint solver, relational data store, graphical model inference engine, and matrix/tensor computation processor all at once. The InsideOut algorithm is very simple, as shall be described in this paper. Yet, in spite of solving an extremely general problem, its runtime either is as good as or improves upon the best known algorithm for the applications that FAQ specializes to. These corollaries include computational tasks in graphical model inference, matrix/tensor operations, relational joins, and logic. Better yet, InsideOut can be used within any database engine, because it is basically a principled way of rewriting queries. Indeed, it is already part of the LogicBlox database engine, helping efficiently answer traditional database queries, graphical model inference queries, and train a large class of machine learning models inside the database itself.
Behavior-based Navigation of Mobile Robot in Unknown Environments Using Fuzzy Logic and Multi-Objective Optimization
Venue: arXiv cs.RO 2017
Year: 2017

This study proposes behavior-based navigation architecture, named BBFM, to deal with the problem of navigating the mobile robot in unknown environments in the presence of obstacles and local minimum regions. In the architecture, the complex navigation task is split into principal sub-tasks or behaviors. Each behavior is implemented by a fuzzy controller and executed independently to deal with a specific problem of navigation. The fuzzy controller is modified to contain only the fuzzification and inference procedures so that its output is a membership function representing the behavior's objective. The membership functions of all controllers are then used as the objective functions for a multi-objective optimization process to coordinate all behaviors. The result of this process is an overall control signal, which is Pareto-optimal, used to control the robot. A number of simulations, comparisons, and experiments were conducted. The results show that the proposed architecture outperforms some popular behavior-based architectures in term of accuracy, smoothness, traveled distance, and time response.
A Generalized Zero-Forcing Precoder with Successive Dirty-Paper Coding in MISO Broadcast Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider precoder designs for multiuser multiple-input-single-output (MISO) broadcasting channels. Instead of using a traditional linear zero-forcing (ZF) precoder, we propose a generalized ZF (GZF) precoder in conjunction with successive dirty-paper coding (DPC) for data-transmissions, namely, the GZF-DP precoder, where the suffix \lq{}DP\rq{} stands for \lq{}dirty-paper\rq{}. The GZF-DP precoder is designed to generate a band-shaped and lower-triangular effective channel $\vec{F}$ such that only the entries along the main diagonal and the $ν$ first lower-diagonals can take non-zero values. Utilizing the successive DPC, the known non-causal inter-user interferences from the other (up to) $ν$ users are canceled through successive encoding. We analyze optimal GZF-DP precoder designs both for sum-rate and minimum user-rate maximizations. Utilizing Lagrange multipliers, the optimal precoders for both cases are solved in closed-forms in relation to optimal power allocations. For the sum-rate maximization, the optimal power allocation can be found through water-filling, but with modified water-levels depending on the parameter $ν$. While for the minimum user-rate maximization that measures the quality of the service (QoS), the optimal power allocation is directly solved in closed-form which also depends on $ν$. Moreover, we propose two low-complexity user-ordering algorithms for the GZF-DP precoder designs for both maximizations, respectively. We show through numerical results that, the proposed GZF-DP precoder with a small $ν$ ($\leq\!3$) renders significant rate increments compared to the previous precoder designs such as the linear ZF and user-grouping based DPC (UG-DP) precoders.
Optimal Network-Assisted Multi-user DASH Video Streaming
Venue: arXiv cs.NI 2017
Year: 2017

Streaming video is becoming the predominant type of traffic over the Internet with reports forecasting the video content to account for 80% of all traffic by 2019. With significant investment on Internet backbone, the main bottleneck remains at the edge servers (e.g., WiFi access points, small cells, etc.). In this work, we propose and prove the optimality of a multiuser resource allocation mechanism operating at the edge server that minimizes the probability of stalling of video streams due to buffer under-flows. Our proposed policy utilizes Media Presentation Description (MPD) files of clients that are sent in compliant to Dynamic Adaptive Streaming over HTTP (DASH) protocol to be cognizant of the deadlines of each of the media file to be displayed by the clients. Then, the policy schedules the users in the order of their deadlines. After establishing the optimality of this policy to minimize the stalling probability for a network with links associated with fixed loss rates, the utility of the algorithm is verified under realistic network conditions with detailed NS-3 simulations.
Modeling the Ellsberg Paradox by Argument Strength
Venue: arXiv cs.AI 2017
Year: 2017

We present a formal measure of argument strength, which combines the ideas that conclusions of strong arguments are (i) highly probable and (ii) their uncertainty is relatively precise. Likewise, arguments are weak when their conclusion probability is low or when it is highly imprecise. We show how the proposed measure provides a new model of the Ellsberg paradox. Moreover, we further substantiate the psychological plausibility of our approach by an experiment (N = 60). The data show that the proposed measure predicts human inferences in the original Ellsberg task and in corresponding argument strength tasks. Finally, we report qualitative data taken from structured interviews on folk psychological conceptions on what argument strength means.
Fuzzy Authentication using Rank Distance
Venue: arXiv cs.IT 2017
Year: 2017

Fuzzy authentication allows authentication based on the fuzzy matching of two objects, for example based on the similarity of two strings in the Hamming metric, or on the similiarity of two sets in the set difference metric. Aim of this paper is to show other models and algorithms of secure fuzzy authentication, which can be performed using the rank metric. A few schemes are presented which can then be applied in different scenarios and applications.
Counterfactuals, indicative conditionals, and negation under uncertainty: Are there cross-cultural differences?
Venue: arXiv cs.AI 2017
Year: 2017

In this paper we study selected argument forms involving counterfactuals and indicative conditionals under uncertainty. We selected argument forms to explore whether people with an Eastern cultural background reason differently about conditionals compared to Westerners, because of the differences in the location of negations. In a 2x2 between-participants design, 63 Japanese university students were allocated to four groups, crossing indicative conditionals and counterfactuals, and each presented in two random task orders. The data show close agreement between the responses of Easterners and Westerners. The modal responses provide strong support for the hypothesis that conditional probability is the best predictor for counterfactuals and indicative conditionals. Finally, the grand majority of the responses are probabilistically coherent, which endorses the psychological plausibility of choosing coherence-based probability logic as a rationality framework for psychological reasoning research.
Does Nash Envy Immunity
Venue: arXiv cs.GT 2017
Year: 2017

The most popular stability notion in games should be Nash equilibrium under the rationality of players who maximize their own payoff individually. In contrast, in many scenarios, players can be (partly) irrational with some unpredictable factors. Hence a strategy profile can be more robust if it is resilient against certain irrational behaviors. In this paper, we propose a stability notion that is resilient against envy. A strategy profile is said to be envy-proof if each player cannot gain a competitive edge with respect to the change in utility over the other players by deviation. Together with Nash equilibrium and another stability notion called immunity, we show how these separate notions are related to each other, whether they exist in games, and whether and when a strategy profile satisfying these notions can be efficiently found. We answer these questions by starting with the general two player game and extend the discussion for the approximate stability and for the corresponding fault-tolerance notions in multi-player games.
Boosted KZ and LLL Algorithms
Venue: arXiv cs.IT 2017
Year: 2017

There exist two issues among popular lattice reduction (LR) algorithms that should cause our concern. The first one is Korkine-Zolotarev (KZ) and Lenstra-Lenstra-Lovasz (LLL) algorithms may increase the lengths of basis vectors. The other is KZ reduction suffers much worse performance than Minkowski reduction in terms of providing short basis vectors, despite its superior theoretical upper bounds. To address these limitations, we improve the size reduction steps in KZ and LLL to set up two new efficient algorithms, referred to as boosted KZ and LLL, for solving the shortest basis problem (SBP) with exponential and polynomial complexity, respectively. Both of them offer better actual performance than their classic counterparts, and the performance bounds for KZ are also improved. We apply them to designing integer-forcing (IF) linear receivers for multi-input multi-output (MIMO) communications. Our simulations confirm their rate and complexity advantages.
Fast Genetic Algorithms
Venue: arXiv cs.NE 2017
Year: 2017

For genetic algorithms using a bit-string representation of length~$n$, the general recommendation is to take $1/n$ as mutation rate. In this work, we discuss whether this is really justified for multimodal functions. Taking jump functions and the $(1+1)$ evolutionary algorithm as the simplest example, we observe that larger mutation rates give significantly better runtimes. For the $\jump_{m,n}$ function, any mutation rate between $2/n$ and $m/n$ leads to a speed-up at least exponential in $m$ compared to the standard choice. The asymptotically best runtime, obtained from using the mutation rate $m/n$ and leading to a speed-up super-exponential in $m$, is very sensitive to small changes of the mutation rate. Any deviation by a small $(1 \pm \eps)$ factor leads to a slow-down exponential in $m$. Consequently, any fixed mutation rate gives strongly sub-optimal results for most jump functions. Building on this observation, we propose to use a random mutation rate $α/n$, where $α$ is chosen from a power-law distribution. We prove that the $(1+1)$ EA with this heavy-tailed mutation rate optimizes any $\jump_{m,n}$ function in a time that is only a small polynomial (in~$m$) factor above the one stemming from the optimal rate for this $m$. Our heavy-tailed mutation operator yields similar speed-ups (over the best known performance guarantees) for the vertex cover problem in bipartite graphs and the matching problem in general graphs. Following the example of fast simulated annealing, fast evolution strategies, and fast evolutionary programming, we propose to call genetic algorithms using a heavy-tailed mutation operator \emph{fast genetic algorithms}.
A Framework for Dynamic Stability Analysis of Power Systems with Volatile Wind Power
Venue: arXiv cs.SY 2017
Year: 2017

We propose a framework employing stochastic differential equations to facilitate the long-term stability analysis of power grids with intermittent wind power generations. This framework takes into account the discrete dynamics which play a critical role in the long-term stability analysis, incorporates the model of wind speed with different probability distributions, and also develops an approximation methodology (by a deterministic hybrid model) for the stochastic hybrid model to reduce the computational burden brought about by the uncertainty of wind power. The theoretical and numerical studies show that a deterministic hybrid model can provide an accurate trajectory approximation and stability assessments for the stochastic hybrid model under mild conditions. In addition, we discuss the critical cases that the deterministic hybrid model fails and discover that these cases are caused by a violation of the proposed sufficient conditions. Such discussion complements the proposed framework and methodology and also reaffirms the importance of the stochastic hybrid model when the system operates close to its stability limit.
Estimating Dynamic Load Parameters from Ambient PMU Measurements
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, a novel method to estimate dynamic load parameters via ambient PMU measurements is proposed. Unlike conventional parameter identification methods, the proposed algorithm does not require the existence of large disturbance to power systems, and is able to provide up-to-date dynamic load parameters consistently and continuously. The accuracy and robustness of the method are demonstrated through numerical simulations.
Visual-Interactive Similarity Search for Complex Objects by Example of Soccer Player Analysis
Venue: arXiv cs.LG 2017
Year: 2017

The definition of similarity is a key prerequisite when analyzing complex data types in data mining, information retrieval, or machine learning. However, the meaningful definition is often hampered by the complexity of data objects and particularly by different notions of subjective similarity latent in targeted user groups. Taking the example of soccer players, we present a visual-interactive system that learns users' mental models of similarity. In a visual-interactive interface, users are able to label pairs of soccer players with respect to their subjective notion of similarity. Our proposed similarity model automatically learns the respective concept of similarity using an active learning strategy. A visual-interactive retrieval technique is provided to validate the model and to execute downstream retrieval tasks for soccer player analysis. The applicability of the approach is demonstrated in different evaluation strategies, including usage scenarions and cross-validation tests.